/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    // 记录当前位置 左边/右边 最高的柱子
    let memo_left = [],
        memo_right = []

    memo_left[0] = height[0]
    memo_right[height.length - 1] = height[height.length - 1]

    for (let i = 1; i < height.length; i++) {
        memo_left[i] = Math.max(memo_left[i - 1], height[i])
    }

    for (let j = height.length - 2; j >= 0; j--) {
        memo_right[j] = Math.max(memo_right[j + 1], height[j])
    }

    // 每个位置的装水量 = min{左边最高柱子，右边最高柱子} - 该位置柱子
    let ans = 0
    for (let i = 0; i < height.length; i++) {
        ans += Math.max(0, Math.min(memo_left[i], memo_right[i]) - height[i])
    }
    return ans
}

